package offer;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class Offer59 {

    //TODO:2023/8/1 超时了
    public int[] maxSlidingWindow(int[] nums, int k) {
        int length = nums.length;
        int[] res = new int[length - k + 1];
        for (int i = 0; i < length - k + 1; i++) {
            int[] temp = Arrays.copyOfRange(nums, i, i + k);
            Arrays.sort(temp);
//            int []  sorted=Arrays.sort(temp);
            res[i] = temp[k - 1];
        }
        return res;
    }

    public int[] maxSlidingWindow1(int[] nums, int k) {
        if(nums.length == 0 || k == 0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];

        for(int i = 0; i < k; i++) { // 未形成窗口
            while(!deque.isEmpty() && deque.peekLast() < nums[i])
                deque.removeLast();
            deque.addLast(nums[i]);
        }
//TODO:2023/10/10 保证窗口中的第一位元素始终是最大的那一个
        res[0] = deque.peekFirst();

        for(int i = k; i < nums.length; i++) { // 形成窗口后

            //TODO:2023/8/1 下面这两句不能少  少了的话 [1,-1]  k=1  这个数组输出的就是【1，1】 实际应该输出的为[1,-1]
//            if(deque.peekFirst() == nums[i - k])
//                deque.removeFirst();
            while(!deque.isEmpty() && deque.peekLast() < nums[i])
                deque.removeLast();
            deque.addLast(nums[i]);
            res[i - k + 1] = deque.peekFirst();
        }
        return res;
    }

    public static void main(String[] args) {
        Offer59 offer59 = new Offer59();
        int[] arr={1,3,-1,-3,2,3,6,7};
        int[] ints = offer59.maxSlidingWindow1(arr, 3);
        for (int a:ints) {
            System.out.println(a);
        }
    }



}